So, how do we do the search?

It's easy.

We're searching the space of partial assignments by doing just assigning one variable at a

time, which has a lot of nice properties.

The probably most important one is that all the solutions will appear at the same depth,

namely after n variables.

So doco depth 81 for others different depth.

So we have this, we can, the important thing is we can just employ depth first search because

depth of this tree is finite.

Very nice.

No going from ARRA to CPU to ARRA to CPU and so on.

All of those kind of things don't appear here.

Good.

So what do we do?

We do, I'm sorry, yes?

I wanted to ask in the last line of the slide, the exclamation mark after nd to the power

of n, is this a faculty or is this actually a pronunciation?

Yeah, nice.

Okay, let's see.

Actually in English it's not faculty but factorial.

Okay, good.

So backtracking search is just depth first search.

Just the way we implement it.

So the idea here, the thing to realize is that you have a choice in what variable to

extend and even more importantly, if you choose the wrong variable, you can still choose the

right variable later.

So you're not losing anything.

So we have a very well-natured search space.

If you think about it from the level of the state space, no matter what we do, in which

order we do the variables, we'll always end up in a situation where we have zero variables

left and we're not losing anything by reordering, which is good because that gives us a choice.

If we had to consider all the paths, then we would have to systematically explore them

and choice wouldn't come in here.

This is something that you should, I've said this before, but it's something to keep in

mind.

There are two kinds of non-determinism when you're doing search trees.

One is called the don't know non-determinism.

You don't know which one to pick.

It's just the kind of bad one.

That means since you don't know, you have to explore all of them.

And then there's don't care non-determinism, which means whatever you do, you're doing

the right thing.

You don't have to worry about those.

That gives you a choice.

And in this case, this property of being commutative actually means that you're in the good situation.

You have a don't care non-determinism.

Whether you do this variable first or that variable first, you're not actually losing

anything.

You can always come back, which means that if those two don't care alternatives or those

81 don't care alternatives, if they have different costs involved to them, you can safely just